package com.sunny.l65;

/**
 * @Author zsunny
 * @Date 2018/9/19 17:20
 * @Mail zsunny@yeah.net
 */
public class Solution {
    public int largestRectangleArea(int[] height) {

        if(null == height || 0 == height.length)
            return 0;
        int len = height.length;
        int[] left = new int[len];
        int[] right = new int[len];
        left[0] = 0;
        for(int i=1;i<len;i++){
            int ind = i;
            while (ind > 0 && height[i] <= height[ind-1]){
                ind = left[ind-1];
            }
            left[i] = ind;
        }
        right[len-1] = len-1;
        for(int i=len-2;i>=0;i--){
            int ind = i;
            while (ind < len-1 && height[i] <= height[ind+1]){
                ind = right[ind+1];
            }
            right[i] = ind;
        }
        int res = 0;
        for(int i=0;i<len;i++){
            int tmpRes = height[i]*(right[i]-left[i]+1);
            if(tmpRes > res){
                res = tmpRes;
            }
        }
        return res;
    }
}
